import org.junit.Test

//给定一个非负整数数组，你最初位于数组的第一个位置。
//
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。 
//
// 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 
//
// 假设你总是可以到达数组的最后一个位置。 
//
// 
//
// 示例 1: 
//
// 
//输入: [2,3,1,1,4]
//输出: 2
//解释: 跳到最后一个位置的最小跳跃数是 2。
//     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
// 
//
// 示例 2: 
//
// 
//输入: [2,3,0,1,4]
//输出: 2
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 105 
// 
// Related Topics 贪心 数组 动态规划 
// 👍 1053 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class SolutionJump {
    @Test
    fun main() {
        println(jump(intArrayOf(3, 2, 1)))
        println(jump(intArrayOf(1, 2)))
        println(jump(intArrayOf(2, 3, 1, 1, 4)))
        println(jump(intArrayOf(2, 3, 0, 1, 4)))
    }

    fun jump(nums: IntArray): Int {
        // 跳跃n次的最大下标
        val dp = IntArray(nums.size + 1)
        dp[0] = 0
        dp[1] = nums[0]
        if (nums.size == 1) {
            return 0
        }
        if (nums.size == 2 || dp[1] >= nums.size - 1) {
            return 1
        }
        // 跳跃次数
        // 上上次跳跃到上次跳跃中间的路，可以重新计算
        // 上次是最大跳转，如2，4，3.中间可能漏4.给一次机会重新计算
        for (i in 2..nums.size) {
            // 下标
            var temp = dp[i - 1] + nums[dp[i - 1]]
            for (j in dp[i - 2]..dp[i - 1]) {
                temp = temp.coerceAtLeast(j + nums[j])
            }
            dp[i] = temp
            if (temp >= nums.size - 1) {
                return i
            }
        }
        return nums.size - 1
        TODO()
    }
}
//leetcode submit region end(Prohibit modification and deletion)
